题目描述

小$W$喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书，这本书一共有$P$页，页码范围为$0 \cdots P-1$。

小$W$很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用NOI2012上学习的线性同余法生成一个序列，来决定每天具体读哪一页。

我们用$Xi$来表示通过这种方法生成出来的第$i$个数，也即小$W$第$i$天会读哪一页。这个方法需要设置$3$个参数$a,b,X1$，满足$0\leq a,b,X1\leq p-1$，且$a,b,X1$都是整数。按照下面的公式生成出来一系列的整数：$X_{i+1} \equiv aX_i+b \pmod p$其中$mod$表示取余操作。

但是这种方法可能导致某两天读的页码一样。

小W要读这本书的第$t$页，所以他想知道最早在哪一天能读到第$T$页，或者指出他永远不会读到第$t$页。

输入输出格式

输入格式：

输入含有多组数据，第一行一个正整数$T$，表示这个测试点内的数据组数。

接下来$T$行，每行有五个整数$p$，$a$，$b$，$X1$，$t$，表示一组数据。保证$X1$和$t$都是合法的页码。 注意：$P$一定为质数

输出格式：

共$T$行，每行一个整数表示他最早读到第$t$页是哪一天。如果他永远不会读到第$t$页，输出$-1$。

输入输出样例

输入样例#1：
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1
输出样例#1：
1
3
-1

说明

$0≤a≤P−1,0≤b≤P−1,2≤P≤10^9$

前言

致敬自己的$16$次提交，漏洞百出

解题思路

这种题目，当然就是找规律套路题啊

有经验就会知道这是一道BSGS的题 找BSGS找到的不是BSGS是什么

最复杂的就是颓推公式了

先随便从$x_1$开始写几组

$x_1=x_1$ 题目已经给出了

$x_2=ax_1+b$

$x_3=a^2x_1+ab+b$

$x_4=a^3x_1+a^2b+ab+b$

好像就可以得出结论了

对于后面这一串东东，如果上过小学学过等比数列求和公式的巨蛤都知道

那么是不是可以开始狂颓公式了

1、换元（这绝对不是高中数学课

然后把上面那个代入

疯狂搞一搞，把$a^{i-1}$搞出来

这样我们就可以按照普通的$BSGS$求，把结果$+1$即可

然后就很OK了

然鹅并没完，（不要问为什么，否则我也不会提交16次了

考虑几种特殊情况：

$1、x_1=t$

第一天就可以读到，输出1，其实也没是什么影响，因为结果还是一样的

$2、a=1$

这就变成了$x_1+k·b \equiv t(mod\ p)$，费马小定理求一下就好了，注意无解的情况——也就是$b=0$

$3、a=0$

傻子都知道和$x_1$无关了，这时只要判断一下$b==t$，则第二天就能读到$t$，否则读一辈子都读不完（那就别读了

Code：

#include<bits/stdc++.h>//这里原题中的t用r表示
#define rgt register
#define ll long long
#define N 100007
using namespace std;
int head[N],nxt[N],val[N],num[N];//用hash表存会快一点，虽然可以用unordered_map
int T,t,ans;
ll a,b,r,p,x,Mol,Den,res;//Mol是分子，Den是分母，（鬼畜的变量名
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void Insert(rgt int x,rgt int y) {//插入，链式前向星
    nxt[++t]=head[x%N],head[x%N]=t;
    val[t]=x,num[t]=y;
}
inline int Search(rgt int x) {//查询，理论上是挺快的
    for(rgt int i=head[x%N];i;i=nxt[i])
        if(val[i]==x) return num[i];
    return -1;
}
inline ll Pow(rgt ll a,rgt int b) {//快速幂
    rgt ll res=1;
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p,b>>=1;
    }
    return res;
}
inline void Init() {//初始化
    memset(head,0,sizeof(head)),t=0;//t用于链式前向星，原来的t代码中用r表示
    Mol=((r-r*a-b)%p+p)%p,Den=Pow(((x-a*x-b)%p+p)%p,p-2);//求出右边那一大串东东
    b=Mol*Den%p;//现在就变成了a^x≡b(mod p)
}
inline int BSGS() {
    Init();
    if(b==1) return 0;//有这个下文x==r的特判就可以省去
    rgt int i,j,t;
    t=sqrt(p)+1,res=b;
    for(i=0;i<t;i++) Insert(res,i),res=res*a%p;
    a=Pow(a,t),res=1;
    if(!a) return (!b)?1:-1;
    for(i=0;i<=t;i++) {
        j=Search(res);
        if(j>=0&&i*t-j>=0) return i*t-j;
        res=res*a%p;
    }
    return -1;
}
int main()
{
    T=read();
    while(T--)
    {
        p=read(),a=read(),b=read(),x=read(),r=read();
        if(x==r) {printf("1\n");continue;}
        if(a==1) {

            if(!b) printf("-1\n");
            else
            {
                r=((r-x)%p+p)%p;
                printf("%lld\n",r*Pow(b,p-2)%p+1);
            }
            continue;
        }
        if(!a) {
            if(b==r) printf("2\n");
            else printf("-1\n");
            continue;
        }
        ans=BSGS();
        if(~ans) printf("%d\n",ans+1);//答案记得+1
        else printf("-1\n");
    }
    return 0;
}

devil.